package algorithm.backtracking.leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * 回溯法解决组合问题
 * LeetCode77-在n个数字中选取k个不重复元素
 * @author yuisama
 * @date 2021/12/28 15:07
 **/
public class Num77 {
    private List<List<Integer>> ret = new LinkedList<>();
    private LinkedList<Integer> cur = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        combineHelper(n,k,1,cur);
        return ret;
    }

    /**
     * 求解C(n,k)问题
     * @param n
     * @param k
     * @param start 当前选取的数
     * @param cur 之前选好的数
     */
    private void combineHelper(int n, int k, int start, LinkedList<Integer> cur) {
        // 终止条件，已经走到叶子节点，cur中保存了当前选好的k个不相同的数
        if (cur.size() == k) {
            ret.add(new LinkedList<>(cur));
            return;
        }
//        for (int i = start; i <= n; i++) {
//            cur.addLast(i);
//            // 继续向下搜素
//            combineHelper(n,k,i + 1,cur);
//            // 回溯，继续取下一个元素
//            cur.removeLast();
//        }
        // 剪枝
        // cur.size()表示已经选取的元素个数了，剩下未选取的元素个数为k - cur.size()个
        // 因此在[i..n]中至少还有k - cur.size()个元素可取
        // 因此循环的终止条件为:i <= n - (k - cur.size()) + 1
        for (int i = start; i <= n - (k - cur.size()) + 1; i++) {
            cur.addLast(i);
            // 继续向下搜素
            combineHelper(n,k,i + 1,cur);
            // 回溯，继续取下一个元素
            cur.removeLast();
        }
    }
}